import java.util.LinkedList;

public class LeetCode98 {
    //中序遍历非递归实现
    public boolean isValidBST(TreeNode node) {
        if (node == null) {
            return true;
        }
        TreeNode p = node; // 记录当前节点的值
        LinkedList<TreeNode> stack = new LinkedList<>();
        long prev = Long.MIN_VALUE; //记录上一个节点的值
        while (p != null || !stack.isEmpty()) {
            if (p != null) {
                stack.push(p);
                p = p.left;
            } else {
                TreeNode pop = stack.pop();
                //处理值
                if (prev >= pop.val) {
                    return false;
                }
                //如果小于当前值 更新prev
                prev = pop.val;
                p = pop.right;

            }
        }
        return true;
    }

    long prev = Long.MIN_VALUE;
    //中序遍历递归实现
    public boolean isValidBST2(TreeNode node) {
        if (node == null) {
            return true;
        }
        // 一旦左子树验证失败，立即返回false，不再继续执行后续代码。
        if (!isValidBST2(node.left)) {
            return false;
        }
        // 如果当前节点不满足BST性质，立即返回false。
        if (prev >= node.val) {
            return false;
        }
        // 更新prev为当前节点的值。
        prev = node.val;
        // 继续验证右子树。
        return isValidBST2(node.right);
    }
}
